class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        const int INT = 0x3f3f3f3f;
        int sum = 0, x1 = INT, x2 = INT, y1 = INT, y2 = INT;
        for (auto x : nums)
        {
            sum += x;
            if (x % 3 == 1)
            {
                if (x < x1) x2 = x1, x1 = x;
                else if (x < x2) x2 = x;
            }
            else if (x % 3 == 2)
            {
                if (x < y1) y2 = y1, y1 = x;
                else if (x < y2) y2 = x;
            }
        }

        if (sum % 3 == 1)
        {
            return max(sum - x1, sum - y1 - y2);
        }
        else if (sum % 3 == 2)
        {
            return max(sum - y1, sum - x1 - x2);
        }
        else
        {
            return sum;
        }
    }
};